class Solution {
public:
    unordered_set<int> s;
    unordered_map<int, unordered_map<int, pair<bool, bool>>> dp;
    bool canCross(vector<int>& stones) {
        for (auto& x : stones) s.insert(x);
        if (stones[1] - stones[0] > 1) return 0;
        return dfs(stones[1], 1, stones.back());
    }
    bool dfs(int pos, int k, int end)
    {
        if (pos == end) return 1;
        if (dp[pos][k].second) return dp[pos][k].first;
        if (s.find(pos) == s.end()) return 0;
        dp[pos][k].second = 1;
        if (s.find(pos + k) != s.end())
        {
            if (dfs(pos + k, k, end)) return dp[pos][k].first = 1;
        }
        if (s.find(pos + k + 1) != s.end())
        {
            if (dfs(pos + k + 1, k + 1, end)) return dp[pos][k].first = 1;
        }
        if (s.find(pos + k - 1) != s.end())
        {
            if (dfs(pos + k - 1, k - 1, end)) return dp[pos][k].first = 1;
        }
        return dp[pos][k].first = 0;
    }
};